0638. 大礼包【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 记忆化搜索

1. 📝 题目描述

• leetcode

在 LeetCode 商店中， 有 n 件在售的物品。每件物品都有对应的价格。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。

给你一个整数数组 price 表示物品价格，其中 price[i] 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单，其中 needs[i] 是需要购买第 i 件物品的数量。

还有一个数组 special 表示大礼包，special[i] 的长度为 n + 1，其中 special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量，且 special[i][n] （也就是数组中的最后一个整数）为第 i 个大礼包的价格。

返回 确切 满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。任意大礼包可无限次购买。

---

示例 1：

输入：price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
输出：14
解释：有 A 和 B 两种物品，价格分别为 ¥2 和 ¥5。
大礼包 1，你可以以 ¥5 的价格购买 3A 和 0B。
大礼包 2，你可以以 ¥10 的价格购买 1A 和 2B。
需要购买 3 个 A 和 2 个 B， 所以付 ¥10 购买 1A 和 2B（大礼包 2），以及 ¥4 购买 2A。

示例 2：

输入：price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]
输出：11
解释：A，B，C 的价格分别为 ¥2，¥3，¥4。
可以用 ¥4 购买 1A 和 1B，也可以用 ¥9 购买 2A，2B 和 1C。
需要买 1A，2B 和 1C，所以付 ¥4 买 1A 和 1B（大礼包 1），以及 ¥3 购买 1B， ¥4 购买 1C。
不可以购买超出待购清单的物品，尽管购买大礼包 2 更加便宜。

---

提示：

• n == price.length == needs.length
• 1 <= n <= 6
• 0 <= price[i], needs[i] <= 10
• 1 <= special.length <= 100
• special[i].length == n + 1
• 0 <= special[i][j] <= 50
• 生成的输入对于 0 <= j <= n - 1 至少有一个 special[i][j] 非零。

2. 🎯 s.1 - 记忆化搜索

c

// C 语言不适合此记忆化搜索 + 动态哈希题，建议使用 JS/PY
int shoppingOffers(int* price, int priceSize, int** special, int specialSize, int* specialColSize, int* needs, int needsSize) {
    int cost = 0;
    for (int i = 0; i < needsSize; i++) cost += needs[i] * price[i];
    for (int i = 0; i < specialSize; i++) {
        int valid = 1;
        int next[6];
        for (int j = 0; j < needsSize; j++) {
            next[j] = needs[j] - special[i][j];
            if (next[j] < 0) { valid = 0; break; }
        }
        if (valid) {
            int sub = special[i][needsSize] + shoppingOffers(price, priceSize, special, specialSize, specialColSize, next, needsSize);
            if (sub < cost) cost = sub;
        }
    }
    return cost;
}

js

/**
 * @param {number[]} price
 * @param {number[][]} special
 * @param {number[]} needs
 * @return {number}
 */
var shoppingOffers = function (price, special, needs) {
  const memo = new Map()
  const dfs = (needs) => {
    const key = needs.join(',')
    if (memo.has(key)) return memo.get(key)
    let min = needs.reduce((s, n, i) => s + n * price[i], 0)
    for (const sp of special) {
      const next = [...needs]
      let valid = true
      for (let i = 0; i < needs.length; i++) {
        next[i] -= sp[i]
        if (next[i] < 0) {
          valid = false
          break
        }
      }
      if (valid) min = Math.min(min, sp[needs.length] + dfs(next))
    }
    memo.set(key, min)
    return min
  }
  return dfs(needs)
}

py

class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        @cache
        def dfs(needs):
            cost = sum(n * p for n, p in zip(needs, price))
            for sp in special:
                nxt = tuple(n - s for n, s in zip(needs, sp[:-1]))
                if all(x >= 0 for x in nxt):
                    cost = min(cost, sp[-1] + dfs(nxt))
            return cost
        return dfs(tuple(needs))

• 时间复杂度：$O(k\times n^m)$，其中 k 是礼包数，n 是最大需求量，m 是物品种类数
• 空间复杂度：$O(n^m)$，记忆化存储的状态数

算法思路：

• 对每个需求状态，先计算不使用礼包的花费作为上界
• 枚举每个合法礼包，递归求解剩余需求的最小花费
• 用记忆化避免重复计算相同状态